package com.ma.DataStruct;

import java.util.PriorityQueue;

/**
 * 数据流的中位数
 */
public class Solution295 {
    public static void main(String[] args) {
        MedianFinder m = new MedianFinder();
        m.addNum(1);
        m.addNum(2);
        System.out.println(m.findMedian());
        m.addNum(3);
        System.out.println(m.findMedian());
    }
}

class MedianFinder {

    private PriorityQueue<Integer> large;
    private PriorityQueue<Integer> small;


    public MedianFinder() {
        // 小顶堆 数据由小到大排列
        large = new PriorityQueue<>();
        // 大顶堆 数据由大到小排列
        small = new PriorityQueue<>((a, b) -> b - a);

    }

    public void addNum(int num) {
        if(small.size()>=large.size()){
            small.offer(num);
            large.offer(small.poll());
        }else{
            large.offer(num);
            small.offer(large.poll());
        }

    }

    public double findMedian() {
        if (large.size() < small.size()) {
            return small.peek();
        } else if (large.size() > small.size()) {
            return large.peek();
        }
        return (large.peek() + small.peek()) / 2.0;
    }
}